package Leetcode.lc076;

/***
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
 * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * 最小覆盖子串 不定长滑动窗口 hard
 */
class Sloution {
    /***
     *
     * @param s 匹配串
     * @param t 模式串
     * @return
     */
    public String minWindow(String s, String t) {
        char[] charArray = s.toCharArray();
        //128包含所有ASCII字符
        int[] pattern = new int[128];
        int[] target = new int[128];
        int ansleft=-1,ansright=s.length();
        for(char c:t.toCharArray()){
            pattern[c]++;
        }
        int left=0;
        for(int right=0;right<charArray.length;right++){
            target[charArray[right]]++;
            while (isContain(target,pattern)){
                //判断大小
                if(right-left<ansright-ansleft){
                    ansleft=left;
                    ansright=right;
                }
                //剔除左指针内容，左指针++
                target[charArray[left++]]--;
            }
        }
        return ansleft==-1?"":s.substring(ansleft,ansright+1);
    }

    /***
     *   类似于赎金信
     * @param target
     * @param pattern
     * @return
     */
    private boolean isContain(int[] target, int[] pattern) {
        for (int i = 'A'; i <= 'Z'; i++) {
            if (target[i] < pattern[i]) {
                return false;
            }
        }
        for (int i = 'a'; i <= 'z'; i++) {
            if (target[i] < pattern[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Sloution sloution = new Sloution();
        String a="ABCDEC";
        String pattern="ED";
        String contain = sloution.minWindow(a, pattern);
        System.out.print(contain);

    }
    }




